//
// Description: 模拟退火算法模板
// Created by Loading on 2021/7/30.
//

/* 用于求解一些基于全排列等，最优化问题的随机算法 */

// 例题：1815. 得到新鲜甜甜圈的最多组数

#include <bits/stdc++.h>

using namespace std;

// 模拟退火算法最优值
int optimal = 0;

// 计算函数（参数和返回值以 int 为例，根据不同情况调整）
/* 用于按照一定规则计算随机序列的结果 */
int Calc(vector<int> &vec) {
    int res = 0;

    // 计算过程……

    return res;
}

// 评价函数（参数和返回值以 int 为例，根据不同情况调整）
/* 用于评价 上一次计算的值与这一次计算的值 的好坏 */
int Evaluation_Function(int last_value, int current_value) {
    int delta = 0;

    // 计算评价结果过程…… 用 delta 表示
    // 一般地，delta > 0 表示这一次结果较好，delta < 0 表示上一次结果较好

    return delta;
}

// https://baike.baidu.com/item/%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB%E7%AE%97%E6%B3%95/355508?fr=aladdin
/* 模拟退火算法（Simulated Annealing） */
/* 来源于固体退火原理，将固体温度升至最高，而后缓慢降温的过程 */
void SA(vector<int> &vec) {
    // 用 1e6 模拟最高温，1e-5 模拟最低温，0.97 为退火系数，均可调，此循环 832 次
    for (double t = 1e6; t > 1e-5; t *= 0.97) {
        // 随机选取 vec 序列的两个位置
        int i = rand() % vec.size();
        int j = rand() % vec.size();
        // 交换之前序列 计算结果
        int last_value = Calc(vec);
        swap(vec[i], vec[j]);
        // 交换之后序列 计算结果
        int current_value = Calc(vec);
        // 根据实际情况，更新最优值
        // optimal = ……

        //两次结果的差值
        /* 评价函数 */
        int delta = Evaluation_Function(last_value, current_value);
        /* 若交换之后比交换之前效果要差，即 delta < 0 时，根据概率考虑保留，否则一定保留 */
        /* 且当前概率小于一个随机概率 (double) rand() / RAND_MAX，则不保留 */

        /*
         * exp(delta / t) 为当前概率，delta 小于 0，t > 0，
         * t 越小，则越趋于稳定，概率越低，越不容易保留结果；
         * delta 越大，则误差越大，概率越低，越不容易保留结果；
         */
        if (delta < 0 && exp(delta / t) < (double) rand() / RAND_MAX) {
            // 结果不保留，还原交换
            swap(vec[i], vec[j]);
        }
    }
}

int solve() {
    vector<int> vec;
    // 初始化等操作……

    // 调用 30 次模拟退火算法，次数可调
    for (int i = 0; i < 30; ++i) {
        SA(vec);
    }

    return optimal;
}

int main() {
    solve();
}